package com.dbh.alg.algorithm.hot100.二叉树;

import com.dbh.alg.datastructure.queue.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,1,4,null,2], k = 1
 * 输出：1
 * 示例 2：
 *
 *
 * 输入：root = [5,3,6,2,4,null,null,1], k = 3
 * 输出：3
 *
 *
 *
 *
 * 提示：
 *
 * 树中的节点数为 n 。
 * 1 <= k <= n <= 104
 * 0 <= Node.val <= 104
 *
 *
 * 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
 */
public class Leetcode230_二叉搜索树种第K小的元素 {

    public int kthSmallest(TreeNode root, int k) {
        TreeNode curr = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while(curr != null  || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode poll = stack.poll();
                k--;
                if (k == 0) {
                    return poll.val;
                }
                curr = poll.right;
            }
        }
        return curr.val;
    }

}
